#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <fstream>
#include "parametros.h"

#include "func_generales.h"

void Swap(int & i, int & j) // hace le swap si i>j
{
    if (i > j) {
        int aux = i;
        i = j;
        j = aux;
    }
}

void DecreaseMatrix(int ** M, int i, int j) {
    if (i > j) {
        int aux = i;
        i = j;
        j = aux;
    }
    M[i][j]--;
}

void SetMatrix(int ** M, int i, int j, int k) {
    if (i > j) {
        int aux = i;
        i = j;
        j = aux;
    }
    M[i][j] = k;
}

int GetMatrix(int ** M, int i, int j) {
    if (i > j) {
        int aux = i;
        i = j;
        j = aux;
    }
    return M[i][j];
}

int Random(int i, int j) {
    return rand() % (j - i) + i;
};

int Random(int i) {
    return rand() % i;
};

Path * SelectRandom(list<Path*> * L) {
    if (L->size() <= 0) return NULL;

    int index = Random(L->size());

    list<Path*>::iterator it = L->begin();
    advance(it, index);

    Path * elem = *it;
    L->erase(it);

    return elem;
};

int SelectRandom(list<int> * L) {
    if (L->size() <= 0) return -1;

    int index = Random(L->size());

    list<int>::iterator it = L->begin();
    advance(it, index);

    int elem = *it;
    L->erase(it);

    return elem;
};

Path * Random(list<Path*> * L) {
    if (L->size() <= 0) return NULL;

    int index = Random(L->size());

    list<Path*>::iterator it = L->begin();
    advance(it, index);

    return *it;
};

pair<int, int>* SelectRandom(list<pair<int, int>*> * L) {
    if (L->size() <= 0) return NULL;

    int index = Random(L->size());

    list<pair<int, int>*>::iterator it = L->begin();
    advance(it, index);

    pair<int, int>* elem = *it;
    L->erase(it);

    return elem;
};

pair<int, int> * RandomEdge(Path * p) {

    if (p->Size() <= 0) return NULL;

    int index = Random(p->Size() - 1);

    list<int>::iterator it = p->path->begin();
    advance(it, index);

    pair<int, int>* elem = new pair<int, int>();
    elem->first = *it;
    it++;
    elem->second = *it;

    return elem;
}

int RandomNode(Path * p) {

    if (p->Size() <= 0) return -1;

    int index = Random(p->Size());

    list<int>::iterator it = p->path->begin();
    advance(it, index);

    return *it;
}

int Contains(list<int>* l, int elem) {

    for (list<int>::iterator it = l->begin(); it != l->end(); it++)
        if ((*it) == elem) {
            return 1;
        }
    return 0;
}

void DeleteListPath(list<Path*>*& Lp) {
    if (Lp) {
        for (list<Path*>::iterator it = Lp->begin(); it != Lp->end(); ++it)
            delete *it;
        Lp->clear();
        delete Lp;
        Lp = NULL;
    }
};

void DeleteListPairInt(list<pair<int, int>*> *& list_pair) {
    if (list_pair) {
        for (list<pair<int, int>*>::iterator it = list_pair->begin(); it != list_pair->end(); ++it)
            delete *it;
        list_pair->clear();
        delete list_pair;
        list_pair = NULL;
    }
};

void DeleteListInt(list<int> *& l) {
    if (l) {
        l->clear();
        delete l;
        l = NULL;
    }
}

void DeleteMatrix(int **& M, int size) {
    if (M) {
        for (int i = 0; i < size; i++)
            delete[] M[i];

        delete[] M;
        M = NULL;
    }
};

void DeletePair(pair<Graph*, PathMatrix*> *& elem) {
    if (elem) {
        delete elem->first;
        delete elem->second;

        delete elem;
        elem = NULL;
    }
}

void CleanLp(list<Path*>* Lp) {
    if (Lp) {
        for (list<Path*>::iterator it = Lp->begin(); it != Lp->end(); ++it)
            delete *it;
        Lp->clear();
    }
};

void CleanListPairInt(list<pair<int, int>*> * list_pair) {
    if (list_pair) {
        for (list<pair<int, int>*>::iterator it = list_pair->begin(); it != list_pair->end(); ++it)
            delete *it;
        list_pair->clear();
    }
};

void CleanListInt(list<int> * l) {
    if (l) {
        l->clear();
    }
}

void GetSecctionTitle(ifstream & file, Graph * Gp) {
    string line;
    if (file.good()) getline(file, line);
}

void GetSecctionComment(ifstream & file, Graph * Gp) {
    string line;
    if (file.good()) getline(file, line);
    if (!line.compare("SECTION Comment")) {
        if (file.good()) getline(file, line);
        while (line.compare("END"))
            if (file.good()) getline(file, line);
    } else
        cout << "[ERROR][GetSecctionComment]: Invalid format\n";
}

void GetSecctionGraph(ifstream & file, Graph * Gp) {
    string line;
    int int_value1;
    int int_value2;
    int int_value3;
    int error;

    if (file.good()) getline(file, line);
    if (!line.compare("SECTION Graph")) {
        if (file.good()) getline(file, line);
        error = sscanf(line.c_str(), "Nodes %d", &int_value1);
        if (!error || error == EOF) cout << "[ERROR][GetSecctionGraph]: Invalid format" << endl;

        Gp->sizeG = int_value1;

        Gp->_T = new int[Gp->sizeG];
        Gp->W = new int[Gp->sizeG];
        Gp->actived_node = new int[Gp->sizeG];

        Gp->R = new int*[Gp->sizeG];
        Gp->C = new int*[Gp->sizeG];
        Gp->E = new int*[Gp->sizeG];
        for (int i = 0; i < Gp->sizeG; i++) {
            Gp->C[i] = new int[Gp->sizeG];
            Gp->E[i] = new int[Gp->sizeG];
            Gp->R[i] = new int[Gp->sizeG];
        }

        for (int i = 0; i < Gp->sizeG; i++) {
            Gp->_T[i] = 0;
            Gp->W[i] = 0;
            Gp->actived_node[i] = 1;

            for (int j = 0; j < Gp->sizeG; j++) {
                Gp->C[i][j] = 0;
                Gp->E[i][j] = 0;
                Gp->R[i][j] = 0;
            }
        }


        if (file.good()) getline(file, line);
        error = sscanf(line.c_str(), "Edges %d", &int_value1);
        if (!error || error == EOF) cout << "[ERROR][GetSecctionGraph]: Invalid format" << endl;

        if (file.good()) getline(file, line);
        while (line.compare("END")) {
            error = sscanf(line.c_str(), "E %d %d %d", &int_value1, &int_value2, &int_value3);
            if (!error || error == EOF) cout << "[ERROR][GetSecctionGraph]: Invalid format" << endl;

            int_value1--;
            int_value2--;

            if (0 > int_value1 || int_value1 >= Gp->sizeG) cout << "[ERROR][GetSecctionGraph]: Invalid terminal " << int_value1 + 1 << endl;
            if (0 > int_value2 || int_value2 >= Gp->sizeG) cout << "[ERROR][GetSecctionGraph]: Invalid terminal " << int_value1 + 1 << endl;

            if (int_value1 == int_value2) cout << "[ERROR][GetSecctionGraph]: No admitted edge " << "(" << int_value1 + 1 << ", " << int_value2 + 1 << ")" << endl;

            SetMatrix(Gp->C, int_value1, int_value2, int_value3);
            SetMatrix(Gp->E, int_value1, int_value2, 1);

            if (file.good()) getline(file, line);
        }
    } else
        cout << "[ERROR][GetSecctionGraph]: Invalid format" << endl;
}

void GetSecctionTerminals(ifstream & file, Graph * Gp) {
    string line;
    int int_value1;
    int error;

    if (file.good()) getline(file, line);
    if (!line.compare("SECTION Terminals")) {
        if (file.good()) getline(file, line);
        error = sscanf(line.c_str(), "Terminals %d", &int_value1);
        if (!error || error == EOF) cout << "[ERROR][GetSecctionTerminals]: Invalid format" << endl;

        Gp->T = new list<int>;

        if (file.good()) getline(file, line);
        while (line.compare("END")) {
            error = sscanf(line.c_str(), "T %d", &int_value1);
            if (!error || error == EOF) cout << "[ERROR][GetSecctionTerminals]: Invalid format" << endl;

            int_value1--;

            if (0 > int_value1 || int_value1 >= Gp->sizeG) cout << "[ERROR][GetSecctionTerminals]: Invalid terminal " << int_value1 + 1 << endl;
            Gp->T->push_front(int_value1);
            Gp->_T[int_value1] = 1;

            if (file.good()) getline(file, line);
        }
    } else
        cout << "[ERROR][GetSecctionTerminals]: Invalid format" << endl;
}

void GetSecctionRequirementsConnectivity(ifstream & file, Graph * Gp) {
    string line;
    int int_value1;
    int int_value2;
    int int_value3;
    int error;

    if (file.good()) getline(file, line);
    if (!line.compare("SECTION Requirements Connectivity")) {
        if (file.good()) getline(file, line);
        while (line.compare("END")) {
            error = sscanf(line.c_str(), "R %d %d %d", &int_value1, &int_value2, &int_value3);
            if (!error || error == EOF) cout << "[ERROR][GetSecctionRequirementsConnectivity]: Invalid format" << endl;

            int_value1--;
            int_value2--;
            if (!Gp->_T[int_value1]) cout << "[ERROR][GetSecctionRequirementsConnectivity]: No is a terminal " << int_value1 << endl;
            if (!Gp->_T[int_value2]) cout << "[ERROR][GetSecctionRequirementsConnectivity]: No is a terminal " << int_value2 << endl;

            // viejo SetMatrix(Gp->R, int_value1, int_value2, int_value3);
            SetMatrix(Gp->R, int_value1, int_value2, 2);

            //cout << line << "\n";
            if (file.good()) getline(file, line);
        }
    } else
        cout << "[ERROR][GetSecctionRequirementsConnectivity]: Invalid format" << endl;
}

void GetSecctionNodeWeight(ifstream & file, Graph * Gp) {
    string line;
    int int_value1;
    int int_value2;
    int error;

    if (file.good()) getline(file, line);
    if (!line.compare("SECTION Weight Nodes")) {
        if (file.good()) getline(file, line);
        while (line.compare("END")) {
            error = sscanf(line.c_str(), "W %d %d", &int_value1, &int_value2);
            if (!error || error == EOF) cout << "[ERROR][GetSecctionNodeWeight]: Invalid format" << endl;

            int_value1--;
            // parche para costo de nodos 0 Gp->W[int_value1] = int_value2;
            Gp->W[int_value1] = 0;

            //cout << line << "\n";
            if (file.good()) getline(file, line);
        }
    } else
        cout << "[ERROR][GetSecctionNodeWeight]: Invalid format" << endl;
}

void GetSecctionDiameter(ifstream & file, Graph * Gp) {
    string line;
    int int_value1;
    int error;

    if (file.good()) getline(file, line);
    if (!line.compare("SECTION Diameter")) {
        if (file.good()) getline(file, line);
        while (line.compare("END")) {
            error = sscanf(line.c_str(), "D %d", &int_value1);
            if (!error || error == EOF) cout << "[ERROR][GetSecctionDiameter]: Invalid format" << endl;
            Gp->diameter = int_value1;

            //cout << line << "\n";
            if (file.good()) getline(file, line);
        }
    } else
        cout << "[ERROR][GetSecctionDiameter]: Invalid format" << endl;
}

list<Path*>* ClearCopy(list<Path*> *l) {

    list<Path*>* l_out = new list<Path*>;

    if (l != NULL) {
        for (list<Path*>::iterator it = l->begin(); it != l->end(); it++)
            l_out->push_back(new Path(*it));
    }

    return l_out;
}

void FileToGraph(const char * path, Graph * Gp) {
    string line;
    ifstream file(path);

    if (file.is_open() && file.good()) {
        GetSecctionTitle(file, Gp);
        if (file.good()) getline(file, line);

        GetSecctionComment(file, Gp);
        if (file.good()) getline(file, line);

        GetSecctionGraph(file, Gp);
        if (file.good()) getline(file, line);

        GetSecctionTerminals(file, Gp);
        if (file.good()) getline(file, line);

        GetSecctionRequirementsConnectivity(file, Gp);
        if (file.good()) getline(file, line);

        GetSecctionNodeWeight(file, Gp);
        if (file.good()) getline(file, line);

        GetSecctionDiameter(file, Gp);

        Gp->Cost();

        file.close();
    } else {
        cout << "[ERROR][FileToGraph]: Unable to open file" << endl;
        exit(1);
    }
}

bool ExistMiiGreaterThanZero(int ** M, int size) {
    for (int i = 0; i < size; i++)
        for (int j = i; j < size; j++)
            if (M[i][j]) return true;

    return false;
}

void PrintGraph(Graph * G) {
    cout << "Print Graph ////////////////////////////////////////////////////////////////////////" << endl;

    cout << "Size: " << G->sizeG << endl;

    cout << "Connectivity: " << endl;
    for (int i = 0; i < G->sizeG; i++) {
        for (int j = 0; j < G->sizeG; j++)
            cout << G->C[i][j] << " ";
        cout << endl;
    }
    cout << endl;

    cout << "Weigth: " << endl;
    for (int i = 0; i < G->sizeG; i++) {
        cout << G->W[i] << " ";
    }
    cout << endl;
    cout << endl;

    cout << "Enables edge: " << endl;
    for (int i = 0; i < G->sizeG; i++) {
        for (int j = 0; j < G->sizeG; j++)
            cout << G->E[i][j] << " ";
        cout << endl;
    }
    cout << endl;

    cout << "Requirements Connectivity: " << endl;
    for (int i = 0; i < G->sizeG; i++) {
        for (int j = 0; j < G->sizeG; j++)
            cout << G->R[i][j] << " ";
        cout << endl;
    }
    cout << endl;

    cout << "Terminals: " << endl;
    for (list<int>::iterator it = G->T->begin(); it != G->T->end(); ++it)
        cout << *it + 1 << " ";
    cout << endl;

    cout << "Is Terminals: " << endl;
    for (int i = 0; i < G->sizeG; i++) {
        cout << G->_T[i] << " ";
    }
    cout << endl;

    cout << "Diameter: " << G->diameter << endl;

    cout << "Active Nodes: " << endl;
    for (int i = 0; i < G->sizeG; i++) {
        cout << G->actived_node[i] << " ";
    }
    cout << endl;

    cout << "Cost: " << G->Cost() << endl;


    cout << "Print Graph ////////////////////////////////////////////////////////////////////////" << endl;

};

void PrintPath(Path * p) {
    for (list<int>::iterator it = p->path->begin(); it != p->path->end(); ++it)
        cout << *it + 1 << " ";
    cout << endl;
}

void PrintPath(Path *p1, Path *p2) {

    for (list<int>::iterator it = p1->path->begin(); it != p1->path->end(); ++it)
        cout << *it + 1 << " ";

    cout << "  :  ";
    for (list<int>::iterator it = p2->path->begin(); it != p2->path->end(); ++it)
        cout << *it + 1 << " ";

    cout << endl;
}

void PrintListInt(list<int> * l) {
    for (list<int>::iterator it = l->begin(); it != l->end(); ++it)
        cout << *it + 1 << " ";
    cout << endl;
}

void PrintListPath(list<Path *> * Lp) {
    for (list<Path*>::iterator it = Lp->begin(); it != Lp->end(); ++it)
        PrintPath(*it);
}

void PrintListPairInt(list<pair<int, int>*> * l) {
    for (list<pair<int, int>*>::iterator it = l->begin(); it != l->end(); ++it)
        cout << "(" << (*it)->first + 1 << ", " << (*it)->second + 1 << ")" << " " << endl;
    cout << endl;
}

void PrintPartialGraph(Graph * G) {

    cout << "Print Graph ////////////////////////////////////////////////////////////////////////" << endl;
    /*cout << "SECTION Nodes" << endl;
    for(int i=0; i<G->sizeG; i++)
            if(G->actived_node[i]) {
                    if(G->_T[i])
                            cout << "T " << i+1 << endl;
                    else
                            cout << "O " << i+1 << endl;
            }

    cout << "END" << endl;
    cout << endl;*/

    /*cout << "SECTION Requirements Connectivity: "<< endl;
    for(int i=0; i<G->sizeG; i++)
    {
            for(int j=0; j<G->sizeG; j++)
                    cout << G->R[i][j] << " ";
            cout << endl;
    }
    cout << endl;*/


    cout << "SECTION Edges" << endl;
    for (int i = 0; i < G->sizeG; i++)
        if (G->actived_node[i]) {
            for (int j = i; j < G->sizeG; j++)
                if (G->actived_node[j] && G->E[i][j])
                    cout << "E " << i + 1 << " " << j + 1 << endl;
        }
    cout << "END" << endl;

    cout << endl;

    /*cout << "SECTION Cost" << endl;
    cout << "C " << G->Cost() << endl;
    cout << "END" << endl;*/
    cout << "Print Graph ////////////////////////////////////////////////////////////////////////" << endl;
}

void PrintPathMatrix(PathMatrix * PM) {

    cout << "Print Path Matrix ////////////////////////////////////////////////////////////////////////" << endl;
    for (int i = 0; i < PM->sizeP; i++) {
        for (int j = i; j < PM->sizeP; j++) {
            if (!PM->P[i][j]->empty()) {
                cout << "(" << i + 1 << ", " << j + 1 << ")" << endl;
                for (list<Path*>::iterator it = PM->P[i][j]->begin(); it != PM->P[i][j]->end(); ++it)
                    PrintPath(*it);

                cout << endl;
            }
        }
    }
    cout << "Print Path Matrix ////////////////////////////////////////////////////////////////////////" << endl;
}

bool Uncoordinated(Graph * G_sol, PathMatrix * P_sol) {

    for (int i = 0; i < P_sol->sizeP; i++) {
        for (int j = i; j < P_sol->sizeP; j++) {
            for (list<Path*>::iterator it = P_sol->P[i][j]->begin(); it != P_sol->P[i][j]->end(); ++it)
                for (list<int>::iterator itA = (*it)->path->begin(); itA != (*it)->path->end(); ++itA) {
                    if (!G_sol->actived_node[*itA]) {
                        cout << "[ERROR][Uncoordinated]: Nodo no activo   " << G_sol->actived_node[*itA] << "   " << *itA + 1 << endl;
                        return true;
                    }
                }
        }
    }



    list<int>::iterator _itA, end;

    for (int i = 0; i < P_sol->sizeP; i++) {
        for (int j = i; j < P_sol->sizeP; j++) {
            for (list<Path*>::iterator it = P_sol->P[i][j]->begin(); it != P_sol->P[i][j]->end(); ++it) {

                end = (*it)->path->end();
                end--;
                for (list<int>::iterator itA = (*it)->path->begin(); itA != end; ++itA) {

                    _itA = itA;
                    _itA++;
                    //	cout << "itA, _itA: " << *itA << " " << *_itA << endl;
                    if (!GetMatrix(G_sol->E, *itA, *_itA)) {
                        cout << "[ERROR][Uncoordinated]: Arista no activa   " << GetMatrix(G_sol->E, *itA, *_itA) << "   (" << *itA + 1 << ", " << *_itA + 1 << ")" << endl;
                        return true;
                    }
                }
            }
        }
    }



    return false;
}

void imprimirGrafoGLPK(Graph* G, const char* rutaSalida, const char* nombreGrafo) {
    //char* ruta = "/home/emi/grafos/";
    char* rutaCompleta = new char[100];
    sprintf(rutaCompleta, "%s/glpk/%s.dat", rutaSalida, nombreGrafo);

    ofstream file(rutaCompleta);
    if (file.is_open()) {
        if ((G->sizeG > 0) && G->actived_node && G->E && G->_T) {
            // imprimo base
            file << "data;" << endl<< endl;
            file << "set L := 1 2;" << endl;
            //itero sobre LISTA nodos
            file << "set V := " ;
            for (int i = 0; i < G->sizeG; i++) {
                file << i+1 << " ";
            }
            file << ";" << endl;

            file << "set T := " ;
            for (list<int>::iterator it = G->T->begin(); it != G->T->end(); it++) {
                file << *it +1 << " ";
            }
            file << ";" << endl << endl ;


            //itero sobre LISTA nodos
            file << "param C : ";
            //todos los nodos TODO
            for (int i = 0; i < G->sizeG; i++) {
                file << i+1 << " ";
            }
            
            file << ":= " << endl;
            
            for (int i = 0; i < G->sizeG; i++) {
                file << i +1<< " ";
                for (int j = 0; j < G->sizeG; j++){
                    if(i<j){
                        file << G->C[i][j] << " ";
                    }else{
                        file << G->C[j][i] << " ";
                     }
                }
                if(i!=G->sizeG-1){
                    file << endl;
                }
                else{
                    file << ";" << endl;
                }
            }
            //imprime final
        }
        file << endl;
        file.close();
    } else cout << "[ERROR][Graph::Dump]: Unable to open file" << endl;
};
